package com.its.myalgorithm.day01;

/**
 * 插入排序、
 * 0-0 范围上面有序
 * 0-1 范围上有序 如果无序交换
 * 0-2 范围上面有序 当前数看前一个 直到前一个数没有前一个
 * 0-3 范围上面有序
 * 0-arr.length 有序
 */
public class InsertionSort {

    public static void insertionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        //0-i 有序
        for (int i = 0; i < arr.length - 1; i++) {
            //0 ~ 0 有序
            //0 ~ 1 有序 两个数比较有序  1 - 0比较谁大谁往后
            //0 ~ 2 有序 三个数比较有序  2-1 比较谁大谁往后 1-0 比较谁大谁往后
            //0 ~ 3 有序 四个数比较有序 3-2 比较谁大谁往后 2-1 比较谁大谁往后 1-1 比较谁大谁往后
            for (int j = i; j >= 0 && arr[j] > arr[j + 1]; j--) {
                com.its.myalgorithm.day01.ArrayUtils.swap(arr, j, j + 1);
            }
        }
    }

    public static void main(String[] args) {
        int testTime = 500000;
        // 随机数组的长度0～100
        // 值：-100～100
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = com.its.myalgorithm.day01.ArrayUtils.generateRandomArray(maxSize, maxValue);
            int[] arr2 = com.its.myalgorithm.day01.ArrayUtils.copyArray(arr1);
            insertionSort(arr1);
            com.its.myalgorithm.day01.ArrayUtils.comparator(arr2);
            if (!com.its.myalgorithm.day01.ArrayUtils.isEqual(arr1, arr2)) {
                // 打印arr1
                com.its.myalgorithm.day01.ArrayUtils.printArray(arr1);
                // 打印arr2
                com.its.myalgorithm.day01.ArrayUtils.printArray(arr2);
                succeed = false;
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");

    }

}
